1691E - Number of Groups - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
typedef pair<int,int> PII;

struct DSU{
    vector<int> dsu, szx;

    DSU() = default;
    DSU(int n) : dsu(n), szx(n, 1) {
        for (int i = 0; i < n; i ++ ) dsu[i] = i;
    }

    int parent(int i){
        if (dsu[i] == i) return i;
        else return dsu[i] = parent(dsu[i]);
    }

    int size(int i) { return szx[parent(i)]; }
    int operator[](int i) { return parent(i); }
    int num_count(){
        int cnt = 0;
        for (int i = 0; i < dsu.size(); i ++ ) if (dsu[i] == i) cnt ++ ;
        return cnt;
    }

    void unify(int a, int b){
        a = parent(a);
        b = parent(b);
        if (szx[a] < szx[b]) swap(a, b);
        if (a != b) dsu[b] = a, szx[a] += szx[b];
    }
};

struct Point{
    int t, p, pc, id;
    bool close;
    bool operator<(Point &other){
        if (p == other.p) return close < other.close;
        return p < other.p;
    }
};

void solve()
{
    int n; cin >> n;
    vector<Point> points;
    for (int i = 0; i < n; i ++ ){
        int t, l, r; cin >> t >> l >> r;
        points.push_back({t, l, r, i, false});
        points.push_back({t, r, l, i, true});
    }
    sort(points.begin(), points.end());

    DSU dsu(n);
    vector<set<PII>> open(2);
    for (auto &p : points){
        if (p.close) open[p.t].erase({p.p, p.id});
        else {
            open[p.t].insert({p.pc, p.id});
            while (open[p.t ^ 1].size() > 1){
                auto [r, id] = *open[p.t ^ 1].begin();
                dsu.unify(p.id, id);
                open[p.t ^ 1].erase({r, id});
            }
            if (open[p.t ^ 1].size() == 1) dsu.unify(p.id, open[p.t ^ 1].begin()->second);
        }
    }
    cout << dsu.num_count() << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int _T; cin >> _T;
    while (_T -- ) solve();

    return 0;
}